/**
 * Created by zhourh on 2018/9/26.
 *
 * 给定一个二叉树，它的每个结点都存放着一个整数值。

 找出路径和等于给定数值的路径总数。

 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

 示例：

 root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

 10
 /  \
 5   -3
 / \    \
 3   2   11
 / \   \
 3  -2   1

 返回 3。和等于 8 的路径有:

 1.  5 -> 3
 2.  5 -> 2 -> 1
 3.  -3 -> 11

 */
public class PathSumIII {

    public static void main(String[] args) {
        TreeNode root = Converter.convertArray2TreeNode(new Integer[]{10,5,-3,3,2,null,11,3,-2,null,1});
        System.out.println(new PathSumIII().pathSum(root, 8));

    }

    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return root.val == sum ? 1 : 0;
        }

        int left = pathSum(root.left, sum);
        int right = pathSum(root.right, sum);

        return left + right + dfsSumCount(root, sum, 0);
    }

    public int dfsSumCount(TreeNode node, int sum, int current) {
        if (node == null) {
            return 0;
        }

        current += node.val;

        return dfsSumCount(node.left, sum, current) + dfsSumCount(node.right, sum, current) + (current == sum ? 1 : 0);

    }

}


